#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/7/7 10:18
# @USER    : Shengji He
# @File    : PathSum.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        """
        Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the
        values along the path equals the given sum.

        Note: A leaf is a node with no children.

        Example:
            Given the below binary tree and sum = 22,

                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \      \
            7    2      1

            return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

        :param root:
        :param sum:
        :return:
        """
        if not root:
            return False
        return self.helper(root, 0, sum)

    def helper(self, root, ans, sum):
        ans += root.val
        if root.left is None and root.right is None:
            if ans == sum:
                return True
            else:
                return False
        elif root.left is None:
            return self.helper(root.right, ans, sum)
        elif root.right is None:
            return self.helper(root.left, ans, sum)
        else:
            return self.helper(root.left, ans, sum) or self.helper(root.right, ans, sum)


if __name__ == '__main__':
    S = Solution()
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(8)
    root.left.left = TreeNode(11)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.right.right.right = TreeNode(1)

    sum = 22
    print(S.hasPathSum(root, sum))
    print('done')
